package com.lisp.algorithm.book.c12;

public class BinarySearchTree {

	public static void main(String[] args) {
		int a[] = {13, 10, 20, 5, 25, 30, 28, 40, 29};
		for(int i : a) {
			insert(i);
		}
		
		inorderTraverse(root);
	}
	
	static Node root;
	
	public static Node predecessor(Node n) {
		if(n == null) {
			return null;
		}
		if(n.left != null) {
			return max(n.left);
		} else {
			while(n.parent != null && n.parent.left == n) {
				n = n.parent;
			}
			return n.parent;
		}
	}
	
	public static Node successor(Node n) {
		if(n == null) {
			return null;
		}
		if(n.right != null) {
			return min(n.right);
		} else {
			while(n.parent != null && n.parent.right == n) {
				n = n.parent;
			}
			return n.parent;
		}
	}
	
	public static Node max(Node n) {
		if(n == null) {
			return null;
		}
		while(n.right != null) {
			n = n.right;
		}
		return n;
	}
	
	public static Node min(Node n) {
		if(n == null) {
			return null;
		}
		while(n.left != null) {
			n = n.left;
		}
		return n;
	}
	
	public static Node search(int key) {
		Node n = root;
		while(n != null) {
			if(n.key == key) {
				return n;
			} else if(n.key < key) {
				n = n.right;
			} else {
				n = n.left;
			}
		}
		return null;
	}
	
	public static void inorderTraverse(Node n) {
		if(n == null) {
			return;
		}
		inorderTraverse(n.left);
		System.out.print(n.key + "  ");
		inorderTraverse(n.right);
	}
	
	public static void insert(int key) {
		if(root == null) {
			root = new Node(key, null, null, null);
		} else {
			insert(key, root);
		}
	}
	
	private static void insert(int key, Node n) {
		if(key > n.key) {
			if(n.right == null) {
				Node newNode = new Node(key, n, null, null);
				n.right = newNode;
			} else {
				insert(key, n.right);
			}
		} else {
			if(n.left == null) {
				Node newNode = new Node(key, n, null, null);
				n.left = newNode;
			} else {
				insert(key, n.left);
			}
		}
	}
	
	static class Node {
		private int key;
		private Node parent;
		private Node left;
		private Node right;
		
		public Node(int key, Node parent, Node left, Node right) {
			super();
			this.key = key;
			this.parent = parent;
			this.left = left;
			this.right = right;
		}
		
		public String toString() {
			return key + "";
		}
	}
}
